/**
 * 归并
 * 51.数组中的逆序对
 * 
 * 快排
 * 45.把数组排成最小的数
 * **/

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    //51.
    int reversePairs(vector<int> &nums)
    {
#if 0
        // 暴力 O(n^2)
        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] > nums[j]) {
                    ++cnt;
                }
            }
        }
        return cnt;
#endif
        // 归并
        vector<int> temp(nums.size(), 0);
        return mergeSort(nums, temp, 0, nums.size() - 1);
    }

private:
    int mergeSort(vector<int> &nums, vector<int> &temp, int left, int right)
    {
        // 出口
        if (left >= right)
            return 0;
        int mid = left + (right - left) / 2;
        int cnt = mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid + 1, right);
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) { // 相等时无贡献，因此j不动
                temp[k++] = nums[i++];
                cnt += (j - mid - 1); // nums[i]对逆序对的贡献 (left<=i<=mid)
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
            cnt += (j - mid - 1);
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        for (int i = left, k = 0; i <= right; ++i) {
            nums[i] = temp[k++];
        }
        return cnt;
    }

public:
    // 45.
    string minNumber(vector<int> &nums)
    {
        // 快排：自定义规则：x+y<y+x
        int n = nums.size();
        vector<string> strs(n);
        for (int i = 0; i < n; ++i) {
            strs[i] = std::to_string(nums[i]);
        }
        quickSort(strs, 0, n - 1);
        string res;
        for (auto &str : strs) {
            res += str;
        }
        return res;
    }

private:
    void quickSort(vector<string> &strs, int left, int right)
    {
        if (left >= right) {
            return;
        }
        string mark = strs[left];
        int pivot = left;
        for (int i = left; i <= right; ++i) {
            if (strs[i] + mark < mark + strs[i]) {
                ++pivot;
                swap(strs[i], strs[pivot]);
            }
        }
        swap(strs[left], strs[pivot]);
        quickSort(strs, left, pivot - 1);
        quickSort(strs, pivot + 1, right);
    }
};

Solution solve = Solution();

void test51()
{
    vector<int> nums = {3, 2, 4, 5, 0, 1};
    cout << solve.reversePairs(nums) << endl;
}

void test45()
{
    vector<int> nums = {3, 30, 34, 5, 9};
    cout << solve.minNumber(nums) << endl;
}

int main()
{
    // test51();
    test45();
    return 0;
}